public class Solution {

    /**
     * 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
     * 如果数组中不存在目标值 target，返回[-1, -1]。
     * <p>
     * 你必须设计并实现时间复杂度为O(log n)的算法解决此问题。
     */
    public static int[] searchRange(int[] nums, int target) {
        if (nums.length == 0) {
            return new int[]{-1, -1};
        }
        int start = findStart(nums, target, 0, nums.length - 1);
        if (start == -1) {
            return new int[]{-1, -1};
        }
        return new int[]{start, findEnd(nums, target, start, nums.length - 1)};
    }

    public static int findStart(int[] arr, int target, int s, int e) {
        int size = e - s + 1;
        if (size < 6) {
            for (int i = s; i <= e; i++) {
                if (arr[i] == target) {
                    return i;
                }
            }
            return -1;
        } else {
            int mid = (e + s) / 2;
            int midValue = arr[mid];
            if (midValue < target) {
                return findStart(arr, target, mid, e);
            } else if (midValue > target) {
                return findStart(arr, target, s, mid);
            } else {
                int preValue = arr[mid - 1];
                if (preValue < target) {
                    return mid;
                } else {
                    return findStart(arr, target, s, mid);
                }
            }
        }
    }

    public static int findEnd(int[] arr, int target, int s, int e) {
        int size = e - s + 1;
        if (size < 6) {
            for (int i = e; i >= s; i--) {
                if (arr[i] == target) {
                    return i;
                }
            }
            return -1;
        } else {
            int mid = (e + s) / 2;
            int midValue = arr[mid];
            if (midValue == target) {
                return findEnd(arr, target, mid, e);
            } else {
                return findEnd(arr, target, s, mid);
            }
        }
    }

    public static void main(String[] args) {
        int[] arrays = new int[]{5, 7, 7, 7, 8, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,21,21,21,21};
        for (int v : searchRange(new int[]{7,7}, 7)) {
            System.out.print(v + ";");
        }
    }


}